#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n, 1);

        for (int i = 1; i < n; i++)
            for (int j = 0; j <= i; j++)
                if (nums[j] < nums[i]) dp[i] = max(dp[j] + 1, dp[i]);

        int ret = 0;
        for (auto x : dp) ret = max(ret, x);
        return ret;
    }
};